

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>1.4 查找最大或最小的 N 个元素 &mdash; python3-cookbook 3.0.0 documentation</title>
  

  
  
  
  

  

  
  
    

  

  <link rel="stylesheet" href="../_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
    <link rel="index" title="Index" href="../genindex.html" />
    <link rel="search" title="Search" href="../search.html" />
    <link rel="next" title="1.5 实现一个优先级队列" href="p05_implement_a_priority_queue.html" />
    <link rel="prev" title="1.3 保留最后 N 个元素" href="p03_keep_last_n_items.html" /> 

  
  <script src="../_static/js/modernizr.min.js"></script>

</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">

    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search">
          

          
            <a href="../index.html" class="icon icon-home"> python3-cookbook
          

          
          </a>

          
            
            
              <div class="version">
                3.0
              </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <ul class="current">
<li class="toctree-l1 current"><a class="reference internal" href="../chapters/p01_data_structures_algorithms.html">第一章：数据结构和算法</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="p01_unpack_sequence_into_separate_variables.html">1.1 解压序列赋值给多个变量</a></li>
<li class="toctree-l2"><a class="reference internal" href="p02_unpack_elements_from_iterables.html">1.2 解压可迭代对象赋值给多个变量</a></li>
<li class="toctree-l2"><a class="reference internal" href="p03_keep_last_n_items.html">1.3 保留最后 N 个元素</a></li>
<li class="toctree-l2 current"><a class="current reference internal" href="#">1.4 查找最大或最小的 N 个元素</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#id1">问题</a></li>
<li class="toctree-l3"><a class="reference internal" href="#id2">解决方案</a></li>
<li class="toctree-l3"><a class="reference internal" href="#id3">讨论</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="p05_implement_a_priority_queue.html">1.5 实现一个优先级队列</a></li>
<li class="toctree-l2"><a class="reference internal" href="p06_map_keys_to_multiple_values_in_dict.html">1.6 字典中的键映射多个值</a></li>
<li class="toctree-l2"><a class="reference internal" href="p07_keep_dict_in_order.html">1.7 字典排序</a></li>
<li class="toctree-l2"><a class="reference internal" href="p08_calculating_with_dict.html">1.8 字典的运算</a></li>
<li class="toctree-l2"><a class="reference internal" href="p09_find_commonalities_in_dicts.html">1.9 查找两字典的相同点</a></li>
<li class="toctree-l2"><a class="reference internal" href="p10_remove_duplicates_from_seq_order.html">1.10 删除序列相同元素并保持顺序</a></li>
<li class="toctree-l2"><a class="reference internal" href="p11_naming_slice.html">1.11 命名切片</a></li>
<li class="toctree-l2"><a class="reference internal" href="p12_determine_most_freqently_items_in_seq.html">1.12 序列中出现次数最多的元素</a></li>
<li class="toctree-l2"><a class="reference internal" href="p13_sort_list_of_dicts_by_key.html">1.13 通过某个关键字排序一个字典列表</a></li>
<li class="toctree-l2"><a class="reference internal" href="p14_sort_objects_without_compare_support.html">1.14 排序不支持原生比较的对象</a></li>
<li class="toctree-l2"><a class="reference internal" href="p15_group_records_based_on_field.html">1.15 通过某个字段将记录分组</a></li>
<li class="toctree-l2"><a class="reference internal" href="p16_filter_sequence_elements.html">1.16 过滤序列元素</a></li>
<li class="toctree-l2"><a class="reference internal" href="p17_extract_subset_of_dict.html">1.17 从字典中提取子集</a></li>
<li class="toctree-l2"><a class="reference internal" href="p18_map_names_to_sequence_elements.html">1.18 映射名称到序列元素</a></li>
<li class="toctree-l2"><a class="reference internal" href="p19_transform_and_reduce_data_same_time.html">1.19 转换并同时计算数据</a></li>
<li class="toctree-l2"><a class="reference internal" href="p20_combine_multiple_map_to_single_map.html">1.20 合并多个字典或映射</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../chapters/p02_strings_and_text.html">第二章：字符串和文本</a></li>
<li class="toctree-l1"><a class="reference internal" href="../aboutme.html">关于</a></li>
</ul>

            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" aria-label="top navigation">
        
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="../index.html">python3-cookbook</a>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        
          















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="../index.html">Docs</a> &raquo;</li>
        
          <li><a href="../chapters/p01_data_structures_algorithms.html">第一章：数据结构和算法</a> &raquo;</li>
        
      <li>1.4 查找最大或最小的 N 个元素</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
            
            <a href="../_sources/c01/p04_find_largest_or_smallest_n_items.rst.txt" rel="nofollow"> View page source</a>
          
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <div class="section" id="n">
<h1>1.4 查找最大或最小的 N 个元素<a class="headerlink" href="#n" title="Permalink to this headline">¶</a></h1>
<div class="section" id="id1">
<h2>问题<a class="headerlink" href="#id1" title="Permalink to this headline">¶</a></h2>
<p>怎样从一个集合中获得最大或者最小的 N 个元素列表？</p>
</div>
<div class="section" id="id2">
<h2>解决方案<a class="headerlink" href="#id2" title="Permalink to this headline">¶</a></h2>
<p>heapq 模块有两个函数：<code class="docutils literal notranslate"><span class="pre">nlargest()</span></code> 和 <code class="docutils literal notranslate"><span class="pre">nsmallest()</span></code> 可以完美解决这个问题。</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">heapq</span>
<span class="n">nums</span> <span class="o">=</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">8</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">23</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="o">-</span><span class="mi">4</span><span class="p">,</span> <span class="mi">18</span><span class="p">,</span> <span class="mi">23</span><span class="p">,</span> <span class="mi">42</span><span class="p">,</span> <span class="mi">37</span><span class="p">,</span> <span class="mi">2</span><span class="p">]</span>
<span class="k">print</span><span class="p">(</span><span class="n">heapq</span><span class="o">.</span><span class="n">nlargest</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="n">nums</span><span class="p">))</span> <span class="c1"># Prints [42, 37, 23]</span>
<span class="k">print</span><span class="p">(</span><span class="n">heapq</span><span class="o">.</span><span class="n">nsmallest</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="n">nums</span><span class="p">))</span> <span class="c1"># Prints [-4, 1, 2]</span>
</pre></div>
</div>
<p>两个函数都能接受一个关键字参数，用于更复杂的数据结构中：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">portfolio</span> <span class="o">=</span> <span class="p">[</span>
    <span class="p">{</span><span class="s1">&#39;name&#39;</span><span class="p">:</span> <span class="s1">&#39;IBM&#39;</span><span class="p">,</span> <span class="s1">&#39;shares&#39;</span><span class="p">:</span> <span class="mi">100</span><span class="p">,</span> <span class="s1">&#39;price&#39;</span><span class="p">:</span> <span class="mf">91.1</span><span class="p">},</span>
    <span class="p">{</span><span class="s1">&#39;name&#39;</span><span class="p">:</span> <span class="s1">&#39;AAPL&#39;</span><span class="p">,</span> <span class="s1">&#39;shares&#39;</span><span class="p">:</span> <span class="mi">50</span><span class="p">,</span> <span class="s1">&#39;price&#39;</span><span class="p">:</span> <span class="mf">543.22</span><span class="p">},</span>
    <span class="p">{</span><span class="s1">&#39;name&#39;</span><span class="p">:</span> <span class="s1">&#39;FB&#39;</span><span class="p">,</span> <span class="s1">&#39;shares&#39;</span><span class="p">:</span> <span class="mi">200</span><span class="p">,</span> <span class="s1">&#39;price&#39;</span><span class="p">:</span> <span class="mf">21.09</span><span class="p">},</span>
    <span class="p">{</span><span class="s1">&#39;name&#39;</span><span class="p">:</span> <span class="s1">&#39;HPQ&#39;</span><span class="p">,</span> <span class="s1">&#39;shares&#39;</span><span class="p">:</span> <span class="mi">35</span><span class="p">,</span> <span class="s1">&#39;price&#39;</span><span class="p">:</span> <span class="mf">31.75</span><span class="p">},</span>
    <span class="p">{</span><span class="s1">&#39;name&#39;</span><span class="p">:</span> <span class="s1">&#39;YHOO&#39;</span><span class="p">,</span> <span class="s1">&#39;shares&#39;</span><span class="p">:</span> <span class="mi">45</span><span class="p">,</span> <span class="s1">&#39;price&#39;</span><span class="p">:</span> <span class="mf">16.35</span><span class="p">},</span>
    <span class="p">{</span><span class="s1">&#39;name&#39;</span><span class="p">:</span> <span class="s1">&#39;ACME&#39;</span><span class="p">,</span> <span class="s1">&#39;shares&#39;</span><span class="p">:</span> <span class="mi">75</span><span class="p">,</span> <span class="s1">&#39;price&#39;</span><span class="p">:</span> <span class="mf">115.65</span><span class="p">}</span>
<span class="p">]</span>
<span class="n">cheap</span> <span class="o">=</span> <span class="n">heapq</span><span class="o">.</span><span class="n">nsmallest</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="n">portfolio</span><span class="p">,</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">s</span><span class="p">:</span> <span class="n">s</span><span class="p">[</span><span class="s1">&#39;price&#39;</span><span class="p">])</span>
<span class="n">expensive</span> <span class="o">=</span> <span class="n">heapq</span><span class="o">.</span><span class="n">nlargest</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="n">portfolio</span><span class="p">,</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">s</span><span class="p">:</span> <span class="n">s</span><span class="p">[</span><span class="s1">&#39;price&#39;</span><span class="p">])</span>
</pre></div>
</div>
<p>译者注：上面代码在对每个元素进行对比的时候，会以 <code class="docutils literal notranslate"><span class="pre">price</span></code> 的值进行比较。</p>
</div>
<div class="section" id="id3">
<h2>讨论<a class="headerlink" href="#id3" title="Permalink to this headline">¶</a></h2>
<p>如果你想在一个集合中查找最小或最大的 N 个元素，并且 N 小于集合元素数量，那么这些函数提供了很好的性能。
因为在底层实现里面，首先会先将集合数据进行堆排序后放入一个列表中：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">nums</span> <span class="o">=</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">8</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">23</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="o">-</span><span class="mi">4</span><span class="p">,</span> <span class="mi">18</span><span class="p">,</span> <span class="mi">23</span><span class="p">,</span> <span class="mi">42</span><span class="p">,</span> <span class="mi">37</span><span class="p">,</span> <span class="mi">2</span><span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">import</span> <span class="nn">heapq</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">heap</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">nums</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">heapq</span><span class="o">.</span><span class="n">heapify</span><span class="p">(</span><span class="n">heap</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">heap</span>
<span class="go">[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]</span>
<span class="go">&gt;&gt;&gt;</span>
</pre></div>
</div>
<p>堆数据结构最重要的特征是 <code class="docutils literal notranslate"><span class="pre">heap[0]</span></code> 永远是最小的元素。并且剩余的元素可以很容易的通过调用 <code class="docutils literal notranslate"><span class="pre">heapq.heappop()</span></code> 方法得到，
该方法会先将第一个元素弹出来，然后用下一个最小的元素来取代被弹出元素（这种操作时间复杂度仅仅是 O(log N)，N 是堆大小）。
比如，如果想要查找最小的 3 个元素，你可以这样做：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">heapq</span><span class="o">.</span><span class="n">heappop</span><span class="p">(</span><span class="n">heap</span><span class="p">)</span>
<span class="go">-4</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">heapq</span><span class="o">.</span><span class="n">heappop</span><span class="p">(</span><span class="n">heap</span><span class="p">)</span>
<span class="go">1</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">heapq</span><span class="o">.</span><span class="n">heappop</span><span class="p">(</span><span class="n">heap</span><span class="p">)</span>
<span class="go">2</span>
</pre></div>
</div>
<p>当要查找的元素个数相对比较小的时候，函数 <code class="docutils literal notranslate"><span class="pre">nlargest()</span></code> 和 <code class="docutils literal notranslate"><span class="pre">nsmallest()</span></code> 是很合适的。
如果你仅仅想查找唯一的最小或最大（N=1）的元素的话，那么使用 <code class="docutils literal notranslate"><span class="pre">min()</span></code> 和 <code class="docutils literal notranslate"><span class="pre">max()</span></code> 函数会更快些。
类似的，如果 N 的大小和集合大小接近的时候，通常先排序这个集合然后再使用切片操作会更快点
（ <code class="docutils literal notranslate"><span class="pre">sorted(items)[:N]</span></code> 或者是 <code class="docutils literal notranslate"><span class="pre">sorted(items)[-N:]</span></code> ）。
需要在正确场合使用函数 <code class="docutils literal notranslate"><span class="pre">nlargest()</span></code> 和 <code class="docutils literal notranslate"><span class="pre">nsmallest()</span></code> 才能发挥它们的优势
（如果 N 快接近集合大小了，那么使用排序操作会更好些）。</p>
<p>尽管你没有必要一定使用这里的方法，但是堆数据结构的实现是一个很有趣并且值得你深入学习的东西。
基本上只要是数据结构和算法书籍里面都会有提及到。
<code class="docutils literal notranslate"><span class="pre">heapq</span></code> 模块的官方文档里面也详细的介绍了堆数据结构底层的实现细节。</p>
</div>
</div>


           </div>
           
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="p05_implement_a_priority_queue.html" class="btn btn-neutral float-right" title="1.5 实现一个优先级队列" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right"></span></a>
      
      
        <a href="p03_keep_last_n_items.html" class="btn btn-neutral" title="1.3 保留最后 N 个元素" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; Copyright 2017, 熊能.

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. 

</footer>

        </div>
      </div>

    </section>

  </div>
  


  

    <script type="text/javascript">
        var DOCUMENTATION_OPTIONS = {
            URL_ROOT:'../',
            VERSION:'3.0.0',
            LANGUAGE:'None',
            COLLAPSE_INDEX:false,
            FILE_SUFFIX:'.html',
            HAS_SOURCE:  true,
            SOURCELINK_SUFFIX: '.txt'
        };
    </script>
      <script type="text/javascript" src="../_static/jquery.js"></script>
      <script type="text/javascript" src="../_static/underscore.js"></script>
      <script type="text/javascript" src="../_static/doctools.js"></script>

  

  <script type="text/javascript" src="../_static/js/theme.js"></script>

  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script> 

</body>
</html>